package 第二章数据结构.单调队列.id154滑动窗口;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 最后一个例子超时，思路没问题
 * 滑动窗口的最值问题，单调队列
 */
public class Main {
    public static void main(String[]args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[]nums = new int[n];
        for(int i= 0;i<n;i++){
            nums[i] = scanner.nextInt();
        }
        //队列存下标
        Deque<Integer> min_queue = new LinkedList<>();
        int[] min_ans = new int[n];
        Deque<Integer> max_queue = new LinkedList<>();
        int[] max_ans = new int[n];
        int c = 0;
        int b = 0;
        int l = 0;
        int r = 0;
        while ( r < n ){
            int cur = nums[r];
            //左边界右移
            if( r - l + 1 > k){
                l++;
                while (!min_queue.isEmpty() && l > min_queue.peek()){
                    min_queue.poll();
                }
                while (!max_queue.isEmpty() && l > max_queue.peek()){
                    max_queue.poll();
                }
            }
            if(min_queue.isEmpty()){
                min_ans[c++] = nums[r];
                max_ans[b++] = nums[r];
            }else {
                //最小
                while (!min_queue.isEmpty() && nums[r] <= nums[min_queue.peekLast()] ){
                    min_queue.removeLast();
                    //min_queue.remove(min_queue.size());
                }
                if(min_queue.isEmpty()){
                    min_ans[c++] = nums[r];
                }else
                    min_ans[c++] = nums[min_queue.peek()];
                //最大
                while (!max_queue.isEmpty() && nums[r] >= nums[max_queue.peekLast()]){
                    max_queue.removeLast();
                }
                if(max_queue.isEmpty()){
                    max_ans[b++] = nums[r];
                }else
                    max_ans[b++] = nums[max_queue.peek()];
            }
            min_queue.add(r);
            max_queue.add(r);
            r++;
        }

        // 处理输出
        for(int i = k-1;i<n;i++){
            System.out.print( min_ans[i] + " ");
        }
        System.out.println();
        for(int i = k-1;i<n;i++){
            System.out.print(max_ans[i] + " ");
        }
    }

}



